from Crypto.Util.number import *

import random

from random import randint

from gmpy2 import *

from secret import flag

import hashlib

assert b'd3ctf' in flag

Bits = 512

UnKnownBits = 146

class QCG():

    def __init__(self,bit_length):

        p = getPrime(bit_length)

        a = randint(0,p)

        c = randint(0,p)

        self._key = {'a':a,'c':c,'p':p}

        self.secret = randint(0,p)

        self.high = []

    def Qnext(self,num):

        return ((self._key['a'])*num**2+self._key['c'])%self._key['p']

    def hint(self):

        num = self.secret

        for i in range(2):

            num = self.Qnext(num)

            self.high.append(num>>UnKnownBits)

    def get_key(self):

        return self._key

    def get_hint(self):

        return self.high

Q1 = QCG(Bits)

print(Q1.get_key())

#{'a': 3591518680290719943596137190796366296374484536382380061852237064647969442581391967815457547858969187198898670115651116598727939742165753798804458359397101, 'c': 6996824752943994631802515921125382520044917095172009220000813718617441355767447428067985103926211738826304567400243131010272198095205381950589038817395833, 'p': 7386537185240346459857715381835501419533088465984777861268951891482072249822526223542514664598394978163933836402581547418821954407062640385756448408431347}

Q1.hint()

print(Q1.get_hint())

#[67523583999102391286646648674827012089888650576715333147417362919706349137337570430286202361838682309142789833, 70007105679729967877791601360700732661124470473944792680253826569739619391572400148455527621676313801799318422]

enc = bytes_to_long(hashlib.sha512(b'%d'%(secret)).digest())^bytes_to_long(flag)

print(enc)

# 6176615302812247165125832378994890837952704874849571780971393318502417187945089718911116370840334873574762045429920150244413817389304969294624001945527125

from tqdm import tqdm

import itertools

def small_roots(f, bounds, m=1, d=None):

    if not d:

        d = f.degree()

    R = f.base_ring()

    N = R.cardinality()

    f /= f.coefficients().pop(0)

    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())

    for i in range(m + 1):

        base = N ^ (m - i) * f ^ i

        for shifts in itertools.product(range(d), repeat=f.nvariables()):

            g = base * prod(map(power, f.variables(), shifts))

            G.append(g)

    B, monomials = G.coefficient_matrix()

    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]

    for i, factor in enumerate(factors):

        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)

    for i, factor in enumerate(factors):

        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))

    for h in filter(None, B * monomials):

        H.append(h)

        I = H.ideal()

        if I.dimension() == -1:

            H.pop()

        elif I.dimension() == 0:

            roots = []

            for root in I.variety(ring=ZZ):

                root = tuple(R(root[var]) for var in f.variables())

                roots.append(root)

            return roots

    return []

from Crypto.Util.number import long_to_bytes

a=3591518680290719943596137190796366296374484536382380061852237064647969442581391967815457547858969187198898670115651116598727939742165753798804458359397101

c=6996824752943994631802515921125382520044917095172009220000813718617441355767447428067985103926211738826304567400243131010272198095205381950589038817395833

p=7386537185240346459857715381835501419533088465984777861268951891482072249822526223542514664598394978163933836402581547418821954407062640385756448408431347

Fp=Zmod(p)

x_=[67523583999102391286646648674827012089888650576715333147417362919706349137337570430286202361838682309142789833, 70007105679729967877791601360700732661124470473944792680253826569739619391572400148455527621676313801799318422]

PR.<t> = PolynomialRing(Fp)

f = a*t*t+c

PR.<k0, k1> = PolynomialRing(Fp)

s = f(x_[0]*2^146 + k0)-x_[1]*2^146-k1

roots = small_roots(s, (2^146,2^146),m=3,d=6) #这里的 m 和 d 不知道是啥意思，打比赛的时候用了 d=2 然后就没跑出来

x=6023304966622247460261427847144394818572943247946434323275721792843243938440324294324349326166203828252327046668948034768905493329350113405677812338671880

PR.<x0>=PolynomialRing(Fp)

s=f(x0)-x

s.roots()

import hashlib

from Crypto.Util.number import *

secret=[4041175780036883478815867467461047550933982405318965631484489156717330002773568568536902190010839138410185231519872805730895806870604072973967270279033142,

3345361405203462981041847914374453868599106060665812229784462734764742247048957655005612474587555839753748604882708741687926147536458567411789178129398205]

c=[]

for i in range(2):

    c.append(bytes_to_long(hashlib.sha512(b'%d'%(secret[i])).digest()))

enc=6176615302812247165125832378994890837952704874849571780971393318502417187945089718911116370840334873574762045429920150244413817389304969294624001945527125

for i in range(2):

    print(long_to_bytes(enc^c[i]))

from Crypto.Util.number import *

from secret import flag

assert flag.startswith("D3CTF{")

assert flag.endswith("}")

message = bytes_to_long(flag[6:-1])

assert message < 2**64

mask = 0b1010010000001000000010001001010010100100000010000000100010010100

def lfsr_MyCode(R,mask):

    output = (R << 1) & 0xffffffffffffffff

    i = (R ^ mask) & 0xffffffffffffffff

    lastbit = 0

    while i != 0:

        lastbit ^= (i & 1)

        i = i>>1

    output ^= lastbit

    return (output,lastbit)

def lfsr_CopiedfromInternet(R,mask):

    output = (R << 1) & 0xffffffffffffffff

    i = (R & mask) & 0xffffffffffffffff

    lastbit = 0

    while i != 0:

        lastbit ^= (i & 1)

        i = i>>1

    output ^= lastbit

    return (output,lastbit)

f=open("standardResult","w")

R=message

for i in range(35):

    (R, out) = lfsr_CopiedfromInternet(R,mask)

    f.write(str(out))

f.close()

f=open("myResult","w")

R=message

for i in range(35):

    (R, out) = lfsr_MyCode(R,mask)

    f.write(str(out))

f.close()

#Why are the results always different?!!

#Can you help me debug my code? QAQ

#myresult 00100110001000110001101010101001001

#standard 01111101111010111000010010111001101

A = matrix(GF(2),70,64)

T1 = matrix(GF(2),64,64)

T2 = matrix(GF(2),64,64)

for i in range(63):

   T1[i,i+1] = 1

   T2[i,i+1] = 1

T1[-1] = [int(i) for i in

'1010010000001000000010001001010010100100000010000000100010010100']

T2[-1] = [1]*64

E1 = T1^64

E2 = T2^64

r1 = '01111101111010111000010010111001101'

r2 = '00100110001000110001101010101001001'

for i in range(35):

 A[i] = E1[i]

 A[i+35] = E2[i]

 b = [int(i) for i in r1+r2]

ans = A.solve_right(b)

print(ans)

flag = 0

for i in ans:

    flag = flag*2+int(i)

print(int.to_bytes(int(flag),8,'big'))

#D3CTF{LF5Rsuk!}

from Crypto.Util.number import bytes_to_long, getPrime

from secret import msg

from sympy import nextprime

from gmpy2 import invert

from hashlib import md5

flag = 'd3ctf{'+md5(msg).hexdigest()+'}'

p = getPrime(256)

q = getPrime(256)

assert p > q

n = p * q

e = 0x10001

m = bytes_to_long(msg)

c = pow(m, e, n)

N = pow(p, 7) * q

phi = pow(p, 6) * (p - 1) * (q - 1)

d1 = getPrime(2000)

d2 = nextprime(d1 + getPrime(1000))

e1 = invert(d1, phi)

e2 = invert(d2, phi)

print(f'c = {c}')

print(f'N = {N}')

print(f'e1 = {e1}')

print(f'e2 = {e2}')

'''

c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967

N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791

e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029

e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919

'''

from Crypto.Util.number import *

from hashlib import *

c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967

N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791

e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029

e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919

P.<x> = PolynomialRing(Zmod(N))

f = e1*e2*x - (e1-e2)

f = f.monic()

res = int(f.small_roots(X=2**1000, beta=0.75)[0])

p = int(gcd(int(f(res)), N))

p = 81911394167511996830305370213894554209992159667974516868378702592733037962549

q = N // p**7

assert p ** 7 * q == N

phi = (p-1)*(q-1)

d = inverse(65537, phi)

m = int(pow(c, d, p*q))

msg = long_to_bytes(m)

print(msg)

flag = 'd3ctf{'+md5(msg).hexdigest()+'}'

print(flag)